package com.tianyuan.test1;

/**二分查找*/
/**  //todo
 * 搜索插入位置
 * @date 2025/10/27 23:26
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * 输入: nums = [1,3,5,6], target = 5 输出: 2
 * 输入: nums = [1,3,5,6], target = 2 输出: 1
 * 输入: nums = [1,3,5,6], target = 7 输出: 4
 */
class Solution {
    /**
     * 寻找目标值在有序数组中的插入位置
     * @param nums  有序数组（升序排列）
     * @param target  要查找的目标值
     * @return  目标值存在时返回对应索引，不存在时返回应插入的索引
     */
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;  // 获取数组长度
        // 初始化左右指针，left指向数组起始位置，right指向数组末尾
        int left = 0, right = n - 1;
        // 初始化插入位置为数组长度（默认情况：目标值大于所有元素，插入到最后）
        int ans = n;
        // 二分查找循环：当左指针不超过右指针时继续查找
        while (left <= right) {
            // 计算中间位置索引（等价于(left + right)/2，但避免溢出）
            int mid = ((right - left) >> 1) + left;
            // 如果目标值小于等于中间元素，说明插入位置可能在mid或其左侧
            if (target <= nums[mid]) {
                ans = mid;  // 更新插入位置为当前mid
                right = mid - 1;  // 缩小右边界，在左侧继续查找
            } else {
                // 目标值大于中间元素，说明插入位置在mid右侧
                left = mid + 1;  // 缩小左边界，在右侧继续查找
            }
        }
        // 返回最终确定的插入位置
        return ans;
    }







    public static void main(String[] args) {
        Solution solution = new Solution();

        // 测试用例1：目标值存在于数组中
        int[] nums1 = {1, 3, 5, 6};
        int target1 = 5;
        System.out.println("输入: nums = [1,3,5,6], target = 5 输出: " + solution.searchInsert(nums1, target1));

        // 测试用例2：目标值不存在于数组中（插入中间位置）
        int[] nums2 = {1, 3, 5, 6};
        int target2 = 2;
        System.out.println("输入: nums = [1,3,5,6], target = 2 输出: " + solution.searchInsert(nums2, target2));

        // 测试用例3：目标值大于数组中所有元素（插入末尾）
        int[] nums3 = {1, 3, 5, 6};
        int target3 = 7;
        System.out.println("输入: nums = [1,3,5,6], target = 7 输出: " + solution.searchInsert(nums3, target3));
    }
}
